package Niuke;


import java.util.*;

public class redo_4_obscure {
    public static class TreeNode {
      int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
     }
    //53
    public int maxSubArray(int[] nums) {
        if (nums.length==1)
            return nums[0];
        int max=nums[0];
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        for (int i=1;i<nums.length;i++){
            if (dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else
                dp[i]=nums[i];
            max=Math.max(max,dp[i]);
        }
        return max;
    }

    //221
    public int maximalSquare(char[][] matrix) {
        //dp[i][j]  represents the max edge of the square whose right-down corner if matrix[i][j]
        int[][] dp=new int[matrix.length][matrix[0].length];
        boolean flag=false;
        for (int i=0;i<dp.length;i++){
            if (matrix[i][0]=='1') {
                dp[i][0] = 1;
                flag=true;
            }
        }
        for (int j=0;j<dp[0].length;j++){
            if (matrix[0][j]=='1') {
                dp[0][j] = 1;
                flag=true;
            }
        }
        int maxEdge=flag==true?1:0;
        for (int i=1;i<dp.length;i++){
            for (int j=1;j<dp[0].length;j++){
                if (matrix[i][j]=='1'){
                    dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                    maxEdge=Math.max(maxEdge,dp[i][j]);
                }
            }
        }
        return maxEdge*maxEdge;
    }

    //207 课程表
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] pre_courses_count=new int[numCourses];
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0;i< prerequisites.length;i++){
            pre_courses_count[prerequisites[i][0]]++;
            queue.offer(prerequisites[i]);
        }
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i=0;i<size;i++){
                int[] tmp = queue.poll();
                if (pre_courses_count[tmp[1]]==0)
                    pre_courses_count[tmp[0]]--;
                else
                    queue.offer(tmp);
            }
            if (queue.size()==size)
                return false;
        }
        return true;
    }
    //课程表 dfs
    int[] visited;
    List<List<Integer>> edges;
    boolean valid=true;
    public boolean canFinish_dfs(int numCourses, int[][] prerequisites) {
            edges=new LinkedList<>();
            for (int i=0;i<numCourses;i++){
                edges.add(new LinkedList<>());
            }
            visited=new int[numCourses];
            for (int[] info:prerequisites)
                edges.get(info[1]).add(info[0]);
            for (int i=0;i<numCourses&&valid;i++){
                if (visited[i]==0)
                    dfs4vourse(i);
            }
            return valid;
    }
    public void dfs4vourse(int i){
        visited[i]=1;
        List<Integer> integers = edges.get(i);
        for (int u:integers){
            if (visited[u]==0){
                dfs4vourse(u);
                if (!valid)
                    return;
            }else if (visited[u]==1){
                valid=false;
                return;
            }
        }
        visited[i]=2;
    }

    //222

    //this viable represents the level of the whole tree
    int totalLevel;
    public int countNodes(TreeNode root) {
        if(root==null)
            return 0;
        totalLevel=findLeftLevel(root,1);
        return countNodesHelp(root,1);
    }
    //it returns the count of nodes of the tree whose root is node,and it is in level curlevel
    //in the case of the tree alwasys is complete binary tree
    public int countNodesHelp(TreeNode node,int curLevel){
        if (curLevel==totalLevel)
            return 1;
        //represents the left child of the node is full binary tree
        if (findLeftLevel(node.right,curLevel+1)==totalLevel)
            //这里有个坑(1<<(totalLevel-curLevel)-1)+1+countNodesHelp(node.right,curLevel+1);
            //上面的写法是不对的，因为会先算totallevel-curlevel-1，再算移位
            return (1<<(totalLevel-curLevel))+countNodesHelp(node.right,curLevel+1);
            //represents the right child of the node is full2tree
        else
            return countNodesHelp(node.left,curLevel+1)+
                    (1<<(totalLevel-curLevel-1));
    }
    //leftLevel will equals the level of the whole tree when the tree is complete binary tree
    public int findLeftLevel(TreeNode node,int curLevel){
        while (node!=null){
            node=node.left;
            curLevel++;
        }
        return curLevel-1;
    }


    //124
    public int max4pathSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
            if (root==null)
                return 0;
            maxPathSum_help(root);
            return max4pathSum;
    }
    public int maxPathSum_help(TreeNode root){
        if (root==null)
            return 0;
        int l = maxPathSum_help(root.left);
        int r = maxPathSum_help(root.right);
        int curmax= root.val;
        if (l>0&&r>0) {
            max4pathSum = Math.max(max4pathSum, curmax + l + r);
            return Math.max(l,r)+curmax;
        }
        else if (l>0&&r<=0) {
            max4pathSum = Math.max(max4pathSum, curmax + l);
            return curmax+l;
        }
        else if (l<=0&&r>0) {
            max4pathSum = Math.max(max4pathSum, curmax + r);
            return curmax+r;
        }
        else {
            max4pathSum=Math.max(max4pathSum,curmax);
            return curmax;
        }
    }

    //236
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null||p==root||q==root)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left==null)
            return right;
        if (right==null)
            return left;
        return root;

    }

    //264
    public int nthUglyNumber(int n) {
        int[] res=new int[n];
        res[0]=1;
        int p2=0;
        int p3=0;
        int p5=0;
        for (int i=1;i<n;i++){
            res[i]=Math.min(Math.min(res[p2]*2,res[p3]*3),res[p5]*5);
            if (res[i]==res[p2]*2)
                p2++;
            if (res[i]==res[p3]*3)
                p3++;
            if (res[i]==res[p5]*5)
                p5++;
        }
        return res[n-1];

    }

    //287寻找重复数 环
    public int findDuplicate(int[] nums) {
        int i=0;
        int j=0;
        i=nums[i];
        j=nums[nums[j]];
        while (nums[i]!=nums[j]){
            i=nums[i];
            j=nums[nums[j]];
        }
        j=0;
        while (nums[i]!=nums[j]){
            i=nums[i];
            j=nums[j];
        }
        return nums[i];
    }


    //322 零钱兑换1
    public int coinChange(int[] coins, int amount) {
        int[][] dp=new int[coins.length][amount+1];
        for (int i=0;i<coins.length;i++)
            dp[i][0]=0;
        int max=amount+1;
        for (int j=0;j<amount+1;j++)
            dp[0][j]=j%coins[0]==0?j/coins[0]:max;
        //dp
        for (int i=1;i<coins.length;i++){
            for (int j=1;j<amount+1;j++){
                dp[i][j]=dp[i-1][j];
                if (j>=coins[i])
                    dp[i][j]=Math.min(dp[i][j],dp[i][j-coins[i]]+1);
            }
        }
        int res=max;
        for (int i=0;i<coins.length;i++)
            res=Math.min(res,dp[i][amount]);
        return res==max?-1:res;

    }

    //518 零钱兑换2
    public int change(int amount, int[] coins) {
        int[][] dp=new int[coins.length][amount+1];
        for (int i=0;i<coins.length;i++)
            dp[i][0]=1;
        for (int j=0;j<amount+1;j++)
            dp[0][j]=j%coins[0]==0?1:0;
        for (int i=1;i<coins.length;i++){
            for (int j=1;j<amount+1;j++){
                dp[i][j]=dp[i-1][j];
                if (j>=coins[i])
                    dp[i][j]+=dp[i][j-coins[i]];
            }
        }
        return dp[coins.length-1][amount];
    }


    //433

    public int minMutation(String start, String end, String[] bank) {
        //bfs
        HashSet<String> bank_set=new HashSet<>();
        for (String s:bank)
            bank_set.add(s);
        HashSet<String> visited=new HashSet<>();
        Queue<String> queue=new LinkedList<>();
        queue.add(start);
        visited.add(start);
        int res=0;
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size-->0){
                String tmp = queue.poll();
                if (tmp.equals(end))
                    return res;
                char[] change=new char[]{'A','C','G','T'};
                for (int i=0;i<change.length;i++){
                    char[] tmp_arr = tmp.toCharArray();
                    for (int j=0;j< tmp_arr.length;j++){
                        char old_c=tmp_arr[j];
                        tmp_arr[j]=change[i];
                        String s = String.valueOf(tmp_arr);
                        if (bank_set.contains(s)&&!visited.contains(s)){
                            queue.offer(s);
                            visited.add(s);
                        }
                        tmp_arr[j]=old_c;
                    }
                }
            }
            res++;
        }
        return -1;
    }

    //437
    int sum4path;
    public int pathSum(TreeNode root, int targetSum) {
        if (root==null)
            return 0;
        HashMap<Integer,Integer> sum_count=new HashMap<>();
        sum_count.put(0,1);
        process(root,0,sum_count,targetSum);
        return sum4path;
    }
    public void process(TreeNode node, int pre, HashMap<Integer,Integer> sum_count,int target){
        if (node==null)
            return;
        int current=pre+node.val;
        Integer i = sum_count.getOrDefault(current - target, 0);
        sum4path+=i;
        Integer preCount = sum_count.getOrDefault(current, 0);
        sum_count.put(current,preCount+1);
        process(node.left,current,sum_count,target);
        process(node.right,current,sum_count,target);
        sum_count.put(current,sum_count.get(current)-1);
    }

    //438
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length()<p.length())
            return new ArrayList<>();
        ArrayList<Integer> res=new ArrayList<>();
        int[] diff_arr=new int[26];
        for (int i=0;i<p.length();i++){
            diff_arr[s.charAt(i)-'a']++;
            diff_arr[p.charAt(i)-'a']--;
        }
        int diff=0;
        for (int i=0;i<diff_arr.length;i++){
            if (diff_arr[i]!=0)
                diff++;
        }
        if (diff==0)
            res.add(0);
        int len=p.length();
        for (int l=0;l<s.length()-p.length();l++){
            //left move
            if (diff_arr[s.charAt(l)-'a']==1)
                diff--;
            if (diff_arr[s.charAt(l)-'a']==0)
                diff++;
            diff_arr[s.charAt(l)-'a']--;
            //right move
            if (diff_arr[s.charAt(l+len)-'a']==-1)
                diff--;
            if (diff_arr[s.charAt(l+len)-'a']==0)
                diff++;
            diff_arr[s.charAt(l+len)-'a']++;
            if (diff==0)
                //因为上面移动之后，diff代表移动之后窗口的结果
                //所以这里要add的是l+1
                res.add(l+1);
        }
        return res;
    }

    //581
    public int findUnsortedSubarray(int[] nums) {
        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        //find right
        int j=-1;
        for (int i=0;i<nums.length;i++){
            if (nums[i]>=max)
                max=nums[i];
            else
                j=i;
        }
        if (j==-1)
            return 0;
        int l=-1;
        for (int i=nums.length-1;i>=0;i--){
            if (nums[i]<min)
                min=nums[i];
            else
                l=i;
        }
        return j-l+1;
    }


    //621
    public int leastInterval(char[] tasks, int n) {
        int[] hash=new int[26];
        for (char c:tasks)
            hash[c-'A']+=1;
        Arrays.sort(hash);
        int min_len=(n+1)*(hash[25]-1)+1;
        for (int i=24;i>=0;i--)
            min_len+=hash[i]==hash[25]?1:0;
        return Math.max(min_len,tasks.length);
    }

    //1089
    public void duplicateZeros(int[] arr) {
        int count=0;
        int index=0;
        while (count<arr.length){
            if (arr[index]!=0)
                count++;
            else
                count+=2;
            index++;
        }
        index--;
        int j=arr.length-1;
        if (count==arr.length+1){
            arr[j]=0;
            index--;
            j--;
        }
        while (j>=0){
            if (arr[index]==0){
                arr[j]=0;
                arr[j-1]=0;
                j-=2;
                index--;
            }else {
                arr[j--]=arr[index--];
            }
        }

    }


    //offer19

    /*public boolean isMatch(String s, String p) {
        return process4match(s,p,0,0);
    }
    public boolean process4match(String s,String p,int i,int j){
        if (j==p.length())
            return i==s.length();
        //p[j+1]!=*
        if (j==p.length()-1||p.charAt(j+1)!='*')
            return i!=s.length()&&
                    (s.charAt(i)==p.charAt(j)||p.charAt(j)=='.')&&
                    process4match(s,p,i+1,j+1);
        //p[j+1]==*
        while (i!=s.length()&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.')){
            if (process4match(s,p,i,j+2))
                return true;
            i++;
        }
        return process4match(s,p,i,j+2);
    }*/

    //offer 32
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> res=new ArrayList<>();
        if (root==null)
            return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int left4right=1;
        while (!queue.isEmpty()){
            int size = queue.size();
            LinkedList<Integer> tmp=new LinkedList<>();
            while (size>0){
                TreeNode poll = queue.poll();
                int val= poll.val;
                if (poll.left!=null)
                    queue.add(poll.left);
                if (poll.right!=null)
                    queue.add(poll.right);
                if (left4right==1)
                    tmp.offerLast(val);
                else
                    tmp.offerFirst(val);
                size--;
            }
            res.add(tmp);
            left4right^=1;
        }
        return res;
    }




    public static void main(String[] args) {
        new redo_4_obscure().findAnagrams("cbaebabacd","abc");
            new redo_4_obscure().minMutation("AACCGGTT","AAACGGTA",new String[]{"AACCGGTA","AACCGCTA","AAACGGTA"});
            /*TreeNode node=new TreeNode(1);
            node.left=new TreeNode(2);
            node.right=new TreeNode(3);
            int res = new redo_4_obscure().maxPathSum(node);
            System.out.println(res);*/
    }
}
